package org.example.leetcode;

import java.util.*;

/**
 * @version 1.0.0
 * @author: lynn
 * @description:  二叉树中第二小的节点
 * @date: 2021/7/27 9:02
 */
public class LC671 {
    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(2);
        treeNode.left=new TreeNode(2);
        treeNode.right=new TreeNode(2);
        /*treeNode.left.left=new TreeNode(1);
        treeNode.left.right=new TreeNode(4);
        treeNode.right.left=new TreeNode(6);
        treeNode.right.right=new TreeNode(8);*/
        LC671 lc=new LC671();
        System.out.println(lc.findSecondMinimumValue(treeNode));
        lc.findSecondMinimumValueList(treeNode);
    }
    public int findSecondMinimumValue(TreeNode root) {
        Set<Integer> set=new HashSet<>();
        if (root==null){
            return -1;
        }
        Stack<Integer> stack=new Stack<>();
        deepOrderLevel(root,stack,set);
        List<Integer> list=new ArrayList<>(set);
        Collections.sort(list);
        return  list.size()>=2?(list.get(1)==null?-1:list.get(1)):-1;
    }



    private void deepOrderLevel(TreeNode root, Stack<Integer> stack, Set<Integer> list){
        if (root==null) return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while (queue.size()>0){
            int size=queue.size();
            for (int i = 0; i <size ; i++) {
                TreeNode tmp=queue.poll();
                list.add(tmp.val);
                if (tmp.left!=null){
                    queue.offer(tmp.left);
                }
                if (tmp.right!=null){
                    queue.offer(tmp.right);
                }
            }
        }
    }



    public int findSecondMinimumValueList(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if (root==null){
            return -1;
        }
        Stack<Integer> stack=new Stack<>();
        deepOrderLevelList(root,stack,list);
        System.out.println(list);

        return  -1;
    }
    private void deepOrderLevelList(TreeNode root, Stack<Integer> stack, List<List<Integer>> list){
        if (root==null) return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        Boolean flag=true;
        while (queue.size()>0){
            int size=queue.size();
            List<Integer> tmpList=new ArrayList<>();
            for (int i = 0; i <size ; i++) {
                TreeNode tmp=queue.poll();
                tmpList.add(tmp.val);
                if (tmp.left!=null){
                    queue.offer(tmp.left);
                }
                if (tmp.right!=null){
                    queue.offer(tmp.right);
                }
            }
            if (flag){
                list.add(tmpList);
            }else {
               Collections.reverse(tmpList);
               list.add(tmpList);
            }
            flag=!flag;
        }
    }
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){};
        TreeNode(int val){
            this.val=val;
        }
        TreeNode(int val,TreeNode left,TreeNode right){
            this.val=val;
            this.left=left;
            this.right=right;
        }
    }
}
